Day 15 : 非線性規劃問題求解演算法 (2/2)

第 11 屆 iThome 鐵人賽

DAY 15

AI & Data

連接數學與現實世界的橋樑 -- 數學建模系列第 15 篇

11th鐵人賽準牛頓法 dfp法 bfgs法牛頓法

spidyjames

2019-09-16 23:43:42

1223 瀏覽

分享至

今天我們繼續來介紹非線性規劃問題的求解方法，

牛頓法(Newton method)

特色:使用目標函數的二階導數來決定搜尋方向
演算法步驟:

選定 $\bar X^{(0)}$ , 令 $k = 0$ , 設定 $\epsilon > 0$
計算 $\bar C^{(k)} = \nabla f(\bar X^{(k)})$ ，如 $|| \bar C^{(k)} || < \epsilon$ ，則停止迭代程序，否則繼續
計算 $\bar H^{(k)}(\bar X^{(k)})$ ，亦即計算目前變數 $\bar X^{(k)}$ 之Hessian matrix
計算搜尋方向 $\bar d^{(k)} = -[\bar H^{(k)}]^{-1} \bar C^{(k)}$
使用一維搜尋法計算 $\alpha_k$ ，使 $f(\bar X^{(k)} + \alpha_k \bar d^{(k)})$ 為最小
更新變數 $\bar X^{(k+1)} = \bar X^{(k)} + \alpha_k \bar d^{(k)}$ ，令 $k = k + 1$ ，回到步驟2

牛頓法的缺點

要計算到2階導數
需確認反矩陣存在

梯度法、共軛梯度法與牛頓法的比較

準牛頓法(Quasi-Newton method)

將以一階導數的計算來近似或代替Hessian matrix，或其反矩陣的計算，使得準牛頓法兼具梯度法與牛頓法的優點。
在此我們介紹兩種準牛頓法，DFP法與BFGS法。

DFP法(Daviden-Fletcher-Powell)

建議搜尋方向 $\bar d^{(k)}$ 如下:
$\bar d^{(k)} = -\bar A^{(k)} \bar C^{(k)}$
(1)當 $k = 0$ ,可令 $\bar A^{(0 )} = \bar I$ (單位矩陣)
(2)當 $k \ge 1$ ,每次迭代更新 $\bar A^{(k)}$ 如下:
$\bar A^{(k+1)} = \bar A^{(k)} + \bar B^{(k)} + \bar C^{(k)}$
其中，
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20B%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20s%5E%7B(k)%7D%20%5Cbar%20s%5E%7B(k)%5E%7BT%7D%7D%7D%7B(%5Cbar%20s%5E%7B(k)%7D%20%5Cbar%20y%5E%7B(k)%7D)%7D%7D$ ; $https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20z%5E%7B(k)%7D%20%5Cbar%20z%5E%7B(k)%5E%7BT%7D%7D%7D%7B(%5Cbar%20y%5E%7B(k)%7D%20%5Cbar%20z%5E%7B(k)%7D)%7D$
$\bar s^{(k)} = \alpha_k \bar d^{(k)}$ ; $\bar y^{(k)} = \bar c^{(k+1)} - \bar c^{(k)}$
$\bar c^{(k+1)} = \nabla f(\bar x^{(k+1)})$ ; $\bar z^{(k)} = \bar A^{(k)} \bar y^{(k)}$

BFGS法(Broyden-Fletcher-Goldford-shanno)

此法經由求解線性方程式 $\bar H^{(k)} \bar d^{(k)} = - \bar c^{(k)}$ 以求得搜尋方向 $\bar d^{(k)}$ ，其中 $\bar H^{(k)}$ 的計算式如下:
(1)當 $k = 0$ ,可令 $\bar H^{(0)} = \bar I$ (單位矩陣)
(2)當 $k \ge 1$ , $\bar H^{(k)}$ 更新如下，
$\bar H^{(k+1)} = \bar H^{(k)} + \bar D^{(k)} + \bar E^{(k)}$
其中，
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20D%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20y%5E%7B(k)%7D%20%5Cbar%20y%5E%7B(k)%5E%7BT%7D%7D%7D%7B%5Cbar%20y%5E%7B(k)%7D%20%5Cbar%20s%5E%7B(k)%7D%7D$ ; $https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20E%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20c%5E%7B(k)%7D%20%5Cbar%20c%5E%7B(k)%5E%7BT%7D%7D%7D%7B%5Cbar%20c%5E%7B(k)%7D%20%5Cbar%20d%5E%7B(k)%7D%7D$
$\bar s^{(k)} = \alpha_k \bar d^{(k)}$ ; $\bar y^{(k)} = \bar c^{(k+1)} - \bar c^{(k)}$
$\bar c^{(k+1)} = \nabla f(\bar X^{(k+1)})$
$\bar c^{(k)} = \nabla f(\bar X^{(k)})$